Digital as well as traditional printing requires continuous-tone images to be represented by displays and printers that are actually capable of presenting only two, or only a few, distinct tonal levels. Dots must be arranged and printed so that the illusion of the original continuous tone image is presented to the viewer. Digital halftoning provides the mechanism of rendering continuous-tone images with such devices.
1. Rendition
In the last few decades several digital halftoning methods have evolved. Of these established approaches, the best known are matrix-based ordered dither, and error diffusion.
The former can be designed to either cluster or disperse dots, a useful property, but produces a regular, periodically repeating though usually very small cell pattern. This pattern in turn can beat against other periodic structures—such as printmasks, or periodicities in the image data themselves—to generate very conspicuous and undesirable moiré or like patterns.
Error diffusion, on the other hand, advantageously produces only patterns that are aperiodic, and that include very limited low-frequency components. These too are useful properties. Error diffusion, however, also operates by producing dispersed dots—which suffer from start-up delays, extremely directional structures that are sometimes said to appear “wormy” or “crawling”, and also an excessive line smudging. This latter drawback is especially objectionable on high-resolution devices and in line drawings.
The directional patterning is particularly conspicuous and objectionable in midtone regions. There it can sometimes happen to be strongly enough developed to superpose on the printed image quite noticeable phantasms that are completely inappropriate to the input image.
Yet another problem of standard error diffusion is color accuracy. Traditional error diffusion called for printing at each pixel whatever colorant (generally cyan, magenta or yellow—or black) had the highest aggregate signal, including input contone (continuous-tone) color for the subject pixel plus accumulated distributions of color error from earlier-processed pixels.
As pointed out in the above-mentioned '243 patent of Best and Dillinger, such earlier-distributed error flows could “diffuse” over long distances before finally happening to arrive at a pixel where they could contribute to an actual printed colorant. Therefore this selection protocol readily produced sprinklings of pixels of colorants that were irrelevant to the specified contone input—green dots in lemons, blue in lawns, and so forth.
Dillinger and Best showed that this objectionable behavior could be mitigated simply by requiring that the printed colorant or colorants be selected from the primary colors which make up the specified contone input. In fact this tactic works very well to eliminate the specific type of error identified above.
It also implies, however, that even higher levels of earlier-distributed error residuals are flowing in the data array, unrelieved by use in a printout. These unresolved residuals propagate right through—without stopping in—areas where they would already have accumulated enough calorimetric mass to be relieved in a printout, but for the Dillinger/Best constraint.
In consequence, concentrations of specific colorants can appear in areas where the input contone values provide only what might be called an excuse or “justification” for them. These concentrations can be disproportionate to the magnitude of the “excuse”; and also may be even more remote from the original input color components that contributed to the heavy residual error flows.
The Best/Dillinger methodology makes no attempt to avoid the directionality of standard error-diffusion processing, or the resulting sometimes-bizarre shapes or patterns. This problem, however, is addressed by the above-mentioned patent documents of Balser, Pappas and Johnston, and Nakazato—and also of Van Rompuy and Van Hunsel (but not for incremental printing).
Those documents may seem to suggest variation of standard error diffusion—i.e. not the salutary color-constrained refinement of Dillinger and Best—by following a random walk through the data array rather than proceeding systematically in row and column order. This nondirectional processing path yields an output character that is correspondingly nondirectional, which should effectively eliminate the crawling or wormy patterns.
In such variants the distribution of error from each processed pixel need not, at least in principle, be limited to the directions that are adopted in standard error diffusion. Rather the distribution can if desired be omnidirectional; these assumptions in turn lead to determining the final rendered form of the image as the end product of a series of successive approximations to the overall image.
Although such variants are likely to be far more computation-intensive than standard (directional) error diffusion, this drawback need not be fatal—especially not in the context of highest-quality imaging requirements. High-end printers and their typically very demanding applications can accept a certain degree of added processing time in return for markedly improved output quality.
Market interest in desktop printers, digital copiers and other types of reproduction equipment continues to increase. The demand for faster and more efficient halftoning methods has forced algorithm designers to push the current implementations to their limits.
In order to allow further evolution of digital printing to meet future demands, a fundamental change must occur in the halftoning process itself. The challenge is to design a halftoning algorithm that combines the advantages of both traditional categories and can push their limits in an intuitive way that allows for straightforward customization.
Some efforts in that direction, while admirable, have not yet completely achieved the goal. Specifically, the Dillinger/Best constraints make a major improvement in color accuracy by preventing dots of certain colors from printing where those colors are entirely foreign or irrelevant—but do not prevent such dots from printing where the response is merely very disproportionate but not completely irrelevant. Dillinger and Best offer no mitigation of the directionality problems.
The random-walk suggestions of Balser and the others, conversely, may represent a major improvement in non-directionality, and the resulting patterns—but again fail to address the application of color dots that are irrelevant or disproportionate. It has perhaps never been proposed to combine the teachings of these references with those of Best and Dillinger; but even if they were combined there would remain no resolution of the disproportionate response to remote error sources.
Yet another drawback—perhaps not well recognized—of known rendition methods is that properties of the final output image as rendered, in particular the quality and fidelity of the image as it will be printed, may not be assessed, or not assessed adequately, in performing the rendition. As a result the process may produce image quality that does not adequately repay the investment in rendering, either because excess time is spent in the process or because the image is poor—or both.
Still another drawback is that conventional rendering programs, which require relatively high storage capacity, ordinarily make no contribution to the following downstream stage of printing makeready—namely printmasking. Whether implemented in hardware, firmware or software, these two kinds of computation-intensive programs are entirely independent; and the program storage needs are essentially duplicative. In other words the storage is used inefficiently.
Furthermore, apart from storage, the actual processes of marching through the data array are also performed twice—once for rendering and again for masking. This is true even though many of the operations at each pixel, for the two processes, are closely related: establish some measure of proximity for pixels that will be considered “nearby”, and consider the influence of those nearby pixels, and apply some resultant of that influence to a decision about the subject pixel; and, finally, implement that decision.
Again another drawback in some or all conventional rendering is that the process steps are not readily made to take into account the local properties of the input image—for instance its local gray areas and gradients. The resulting image is therefore not fine-tuned for those local properties, or here too the processing may require more computing power or more time than fundamentally necessary. A similar observation applies to handling of interactions between the image data and the rendering, especially some interactions that can cause clustering (graininess in the image) and other undesirable effects.
In addition, some conventional rendering processes that are useful in single-bit binary printing may become quite unwieldy when applied to multilevel printing (e.g. marking systems that use two- or three-bit colorimetric data depth). Hence a further duplication of program storage requirements arises if a single printer is to be provided with marking capability in more than one bit depth. Precisely that kind of versatile operation, however, is particularly advantageous in high-end printers to allow quick, efficient output of a rough draft—or of a commercial-graphics project or other image that intrinsically needs only two or four levels, rather than four or eight.
The foregoing discussion of digital rendition (or “halftoning”) methods is relevant to the present invention, which provides advantageous alternative rendition methods. The invention, however, also has application to digital or “incremental” printing makeready techniques known as “printmasking”. following is a discussion of the reasons for printmasking, and some known considerations for optimizing such masking.
2. Printmasking
To achieve vivid colors in inkjet printing with aqueous inks, and to substantially fill the white space between addressable pixel locations, ample quantities of ink must be deposited. Doing so, however, requires subsequent removal of the water base—by evaporation (and, for some printing media, absorption)—and this drying step can be unduly time consuming.
In addition, if a large amount of ink is put down all at substantially the same time, within each section of an image, related adverse bulk-colorant effects arise: so-called “bleed” of one color into another (particularly noticeable at color boundaries that should be sharp), “blocking” or offset of colorant in one printed image onto the back of an adjacent sheet with consequent sticking of the two sheets together (or of one sheet to pieces of the apparatus or to slipcovers used to protect the imaged sheet), and “cockle” or puckering of the printing medium. Various techniques are known for use together to moderate these adverse drying-time effects and bulk- or gross-colorant effects.
(a) Prior heat-application techniques—Among these techniques is heating the inked medium to accelerate evaporation of the water base or carrier. Heating, however, has limitations of its own; and in turn creates other difficulties due to heat-induced deformation of the printing medium.
Glossy stock warps severely in response to heat, and transparencies too can tolerate somewhat less heating than ordinary paper. Accordingly, heating has provided only limited improvement of drying characteristics for these plastic media.
As to paper, the application of heat and ink causes dimensional changes that affect the quality of the image or graphic. Specifically, it has been found preferable to precondition the paper by application of heat before contact of the ink; if preheating is not provided, so-called “end-of-page handoff” quality defects occur—such defects take the form of a straight image-discontinuity band formed across the bottom of each page when the page bottom is released.
Preheating, however, causes loss of moisture content and resultant shrinking of the paper fibers. To maintain the paper dimensions under these circumstances the paper is held in tension, and this in turn leads to still other dimensional complications and problems.
(b) Prior printmode techniques—Another useful technique is laying down in each pass of the pen only a fraction of the total ink required in each section of the image—so that any areas left white in each pass are filled in by one or more later passes. This tends to control bleed, blocking and cockle by reducing the amount of liquid that is all on the page at any given time, and also may facilitate shortening of drying time.
The specific partial-inking pattern employed in each pass, and the way in which these different patterns add up to a single fully inked image, is known as a “printmode”. Artisans in this field heretofore have developed many different variations and elaborations of printmodes—and in general many of these techniques have been found to introduce their own backward steps for each forward step.
For example, some printmodes such as square or rectangular checkerboard-like patterns tend to create objectionable moiré effects—just as noted earlier for dither masks—when frequencies or harmonics generated within the patterns are close to the frequencies or harmonics of interacting subsystems. Such interfering frequencies may arise, for example, in subsystems sometimes used to help control the paper advance or the pen speed.
(c) Directional effects—Another problem related to printmode techniques is that these techniques, like error diffusion, can produce undesired directional patterning, particularly if printmasks are generated by algorithms which themselves proceed directionally. As will be seen, this problem is avoided inherently through application of the present invention to generate printmasks.
(d) Known technology of printmodes: general introduction—One particularly simple way to divide up a desired amount of ink into more than one pen pass is the checkerboard pattern mentioned above: every other pixel location is printed on one pass, and then the blanks are filled in on the next pass.
To avoid horizontal “banding” problems (and sometimes minimize the moire patterns) discussed above, a printmode may be constructed so that the paper advances between each initial-swath scan of the pen and the corresponding fill-swath scan or scans. In fact this can be done in such a way that each pen scan functions in part as an initial-swath scan (for one portion of the printing medium) and in part as a fill-swath scan.
Once again this technique tends to distribute rather than accumulate print-mechanism error that is impossible or expensive to reduce. The result is to minimize the conspicuousness of—or, in simpler terms, to hide—the error at minimal cost.
(e) Space- and sweep-rotated printmode masks—The pattern used in printing each nozzle section is known as the “printmode mask”. The term “printmode” is more general, usually encompassing a description of a mask, the number of passes required to reach full density and the number of drops per pixel defining “full density”.
A relatively full discussion of so-called “rotation” of masks, including “autorotating” masks in which rotation occurs even though the pen pattern is consistent over the whole pen array and is never changed between passes, appears in patents issued to Lance Cleveland and assigned to Hewlett-Packard.
3. Throughput and Other Handicaps of Conventional Rendition and Printmasking
Yet another backward step that accompanies the benefits of printmodes is a penalty in throughput, or overall printing speed. Throughput is one of the critical competitive vectors for inkjet printers.
One of the main throughput limiters is the need to divide the printing of a given area into several scans, or passes, due mostly to restrictions in the amount of ink that the medium can accept in a single pass, but also to the desire for limiting objectionable artifacts created by registration errors.
Although these facts are well known, an aspect of printmodes that generally goes unrecognized is that much of the throughput degradation for an overall image is incurred only because of masking requirements for just a portion of the image. The rest of the degradation is essentially wasted.
Incremental printers heretofore have been programmed to choose a printing strategy, or printmode, initially—most commonly according to a user's mode selection—and thereafter to use that printmode choice throughout each plot. A printmode, however, represents a trade-off between quality and throughput, given by the choice of number of passes and printing speed.
Choosing the number of passes at the outset, and using it throughout the plot as described above, is therefore a simplification that pays a significant throughput penalty.
The inkjet-printing. “pipeline” is a series of transformations through which image data pass, in order to prepare the data for printing the image. A simplified view of the pipeline has three main steps:                Color-space conversion—The image is transformed from the original color space to match the color capabilities of the printer. In a four-pen printer, for example, an eight-bit-per-pixel RGB image is transformed into an eight-bit-per-pixel CMYK image.        Bit depth reduction, or halftoning—The printer will be able to deposit only a small amount of ink per pixel, typically one, two or three droplets. The pixels in the input image, at eight bits per pixel and a full range of 256 possible colors, most typically have to be converted to a single bit, i.e. a 1 or a 0 (fire or don't fire).                    The halftoning process accomplishes this by selecting the pixels to print so that the average density of drops will give a visual impression which matches the level on the original image. Bit depth reduction is achieved, essentially, by selecting where to print.                        Pass separation, or masking—In most cases the printer cannot print all the drops in one scan across a page, for reasons discussed above. These include constraints on the amount of ink that the printing medium is able to tolerate, the frequency at which the nozzles can fire, and the desire to spread registration errors in such a way that the printed result does not have objectionable artifacts.                    The conventional masking solution to this problem is to scan over the medium several times, each time firing a fraction of the drops and advancing the medium. Thus the word “masking” means, in essence, selecting when to print each drop.                        
There are strong interactions between these last two parts of the printing pipeline. Perhaps the most basic is that they both apply a selection step to the pixels: the halftoning decides which ones will be printed, and the masking decides which ones, out of those, will be printed in a given pass—or, to put in another way, which pixels will be printed in which passes.
Both halftoning and masking algorithms are carefully designed so that the two selections result in pleasing patterns, without discernible artifacts. A problem appears when the two selections are combined, because the combination of two individually pleasing patterns is not necessarily pleasing.
This is probably the most fundamental problem in mask design. The mask designer tries to select the best possible pattern to be deposited at each pass, but in the end the pattern actually printed will be a combination (an “AND” step) of the mask pattern with the pattern selected by the halftoning.
The mask designer, therefore, never really knows how the mask is actually going to look on paper. Beats (interferences) between halftoning and masking at related frequencies are not the only interaction between masking and halftoning.
4. Conclusion, as to Background
In summary, achievement of uniformly excellent inkjet printing continues to be impeded by the above-mentioned problems of directionality, disproportionate color response, absence of quality-information feedback, failure to share storage space and processing steps, and failure to take into account local properties of the image being rendered—as well as the interaction of such properties with the rendering process itself. Thus important aspects of the technology used in the field of the invention remain amenable to useful refinement.